package array_list;

public class MyArrayList implements MyList{
    // 定义属性
    private Long[] array;   // array.length 也就是我们的容量（capacity）
    private int size;       // 保存元素的个数

    // 构造方法
    public MyArrayList() {
        // 容量没有规定，自行定义为 16 个
        this.array = new Long[16];
        // 这一步不是必须的，把数组中的每个位置都初始化成 null
        for (int i = 0; i < array.length; i++) {
            array[i] = null;
        }
        // 元素个数 = 0
        this.size = 0;
    }

    public MyArrayList(int initialCapacity) {
        this.array = new Long[initialCapacity];
        // 这一步不是必须的，把数组中的每个位置都初始化成 null
        for (int i = 0; i < array.length; i++) {
            array[i] = null;
        }
        // 元素个数 = 0
        this.size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    // 时间复杂度：数据规模是 size，时间复杂度是 O(1)

    @Override
    //时间复杂度：数据规模是size，时间复杂度是O(1)
    public boolean add(Long e) {
        // 为 size 赋予一个新的逻辑含义 —— 尾插时的元素的位置
        array[size] = e;
        // 尾插了一个元素，所以元素个数 + 1
        size = size + 1;
        // 返回 true 表示插入成功
        return true;
    }

    @Override
    // 时间复杂度：O(n)
    public void add(int index, Long e) {
        if (index < 0 || index > size) {
            // 下标不合法
            throw new ArrayIndexOutOfBoundsException("下标不合法");
        }
        // 此处，下标一定是合法的
        // 搬家
        // i: 搬家时的出发点
        for (int i = size - 1; i >= index; i--) {
            // array[i] 的元素搬到  array[i + 1]
            array[i + 1] = array[i];
        }
        // 将 e 放到 index 位置
        array[index] = e;
        // 元素个数增加了 1
        size = size + 1;
    }

    @Override
    //时间复杂度：O(n)
    public Long remove(int index) {
        //下标检查
        if(index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException();
        }
        long e = array[index];
        //搬家
        for (int i = index + 1; i < size; i++) {
            array[i - 1] = array[i];
        }
        //将不存在的元素置null
        array[size - 1] = null;
        //元素个数 - 1
        size = size - 1;
        return e;
    }

    @Override
    //时间复杂度：O(n)
    public boolean remove(Long e) {
        //从前向后查找
        for (int i = 0; i < size; i++) {
            //比较array的值与e是否相等
            if(array[i].equals(e)){
                //调用remove方法
                remove(i);
                return true;
            }
        }
        //没找到e
        return false;
    }

    @Override
    //时间复杂度：O(1)
    public Long get(int index) {
        //检查下标是否合法
        if(index < 0 || index >=size){
            throw new ArrayIndexOutOfBoundsException();
        }
        return array[index];
    }

    @Override
    //时间复杂度：O(1)
    public Long set(int index, Long e) {
        //检查下标
        if(index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException();
        }
        long temp = array[index];
        array[index] = e;
        return temp;
    }

    @Override
    //时间复杂度：O(n)
    public int indexOf(Long e) {
        for (int i = 0; i < size; i++) {
            if(array[i].equals(e)){
                return i;
            }
        }
        return -1;
    }

    @Override
    //时间复杂度：O(n)
    public int lastIndexOf(Long e) {
        for (int i = size - 1; i >= 0 ; i++) {
            if(array[i].equals(e)){
                return i;
            }
        }
        return -1;
    }

    @Override
    //时间复杂度：O(n)
    public boolean contains(Long e) {
        return indexOf(e) != -1;
    }

    @Override
    public void clear() {
        //将array中全部置为null
        for (int i = 0; i < size; i++) {
            array[i] = null;
        }
        this.size = 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    //检查顺序表是否合法
    private static void isLegal(MyArrayList list) {
        // 0 <= size <= array.length
        if (list.size < 0) {
            throw new RuntimeException();
        }
        if (list.size > list.array.length) {
            throw new RuntimeException();
        }
        // array[0, size) != null
        for (int i = 0; i < list.size; i++) {
            if (list.array[i] == null) {
                throw new RuntimeException();
            }
        }
        // array[size, array.length) == null
        for (int i = list.size; i < list.array.length; i++) {
            if (list.array[i] != null) {
                throw new RuntimeException();
            }
        }
    }
    //断言顺序表的元素个数一定是
    public static void assertElementsNumber (MyArrayList list,int size){
        if(list.size != size){
            throw new RuntimeException();
        }
    }
    //断言顺序表的指定位置元素一定是
    private static void assertDesignatedSpotElement(MyArrayList list, int index, long e) {
        // Long != long
        // long != long
        if (list.array[index] != e) {
            throw new RuntimeException();
        }
    }

    public static void main(String[] args) {
        // 之所以把测试代码写这里，是方便读取 private 的属性
        MyArrayList list = new MyArrayList();
        isLegal(list);

        // 无参构造方法定义的顺序表，size 应该是 0
        assertElementsNumber(list, 0);

        // 先测试尾插 add()
        boolean r;

        r = list.add(Long.valueOf(100));    // 手动把 int 包装成 Long
        // 检查 r 必须是 true
        if (r == false) {
            throw new RuntimeException();
        }

        isLegal(list);
        assertElementsNumber(list, 1);
        assertDesignatedSpotElement(list, 0, 100);

        r = list.add(200L);         // 编译器自动把 long 包装成 Long
        if (r == false) {
            throw new RuntimeException();
        }

        isLegal(list);
        assertElementsNumber(list, 2);
        assertDesignatedSpotElement(list, 0, 100);
        assertDesignatedSpotElement(list, 1, 200);

        r = list.add(300L);
        if (r == false) {
            throw new RuntimeException();
        }

        isLegal(list);
        assertElementsNumber(list, 3);
        assertDesignatedSpotElement(list, 0, 100);
        assertDesignatedSpotElement(list, 1, 200);
        assertDesignatedSpotElement(list, 2, 300);

        // 测试 根据 index 进行插入 add(int index, Long e)

        // [100, 200, 300]
        list.add(3, 1000L);
        // [100, 200, 300, 1000]
        isLegal(list);
        assertElementsNumber(list, 4);
        assertDesignatedSpotElement(list, 0, 100);
        assertDesignatedSpotElement(list, 1, 200);
        assertDesignatedSpotElement(list, 2, 300);
        assertDesignatedSpotElement(list, 3, 1000);

        // [100, 200, 300, 1000]
        list.add(0, 2000L);
        // [2000, 100, 200, 300, 1000]
        isLegal(list);
        assertElementsNumber(list, 5);
        assertDesignatedSpotElement(list, 0, 2000);
        assertDesignatedSpotElement(list, 1, 100);
        assertDesignatedSpotElement(list, 2, 200);
        assertDesignatedSpotElement(list, 3, 300);
        assertDesignatedSpotElement(list, 4, 1000);

        // [2000, 100, 200, 300, 1000]
        list.add(2, 3000L);
        // [2000, 100, 3000, 200, 300, 1000]
        isLegal(list);
        assertElementsNumber(list, 6);
        assertDesignatedSpotElement(list, 0, 2000);
        assertDesignatedSpotElement(list, 1, 100);
        assertDesignatedSpotElement(list, 2, 3000);
        assertDesignatedSpotElement(list, 3, 200);
        assertDesignatedSpotElement(list, 4, 300);
        assertDesignatedSpotElement(list, 5, 1000);

        // [2000, 100, 3000, 200, 300, 1000]
//        list.add(13, 4000L);    // 非法下标，应该看到 下标越界异常

        // [2000, 100, 3000, 200, 300, 1000]
        Long e = list.remove(2);
        // [2000, 100, 200, 300, 1000]
//        if (e != 3000) {
//            throw new RuntimeException();
//        }
        isLegal(list);
        assertElementsNumber(list, 5);
        assertDesignatedSpotElement(list, 0, 2000);
        assertDesignatedSpotElement(list, 1, 100);
        assertDesignatedSpotElement(list, 2, 200);
        assertDesignatedSpotElement(list, 3, 300);
        assertDesignatedSpotElement(list, 4, 1000);

        // 测试删除 remove(0)  remove(size - 1)

        // [2000, 100, 200, 300, 1000]
        r = list.remove(100L);
        // [2000, 200, 300, 1000]
        if (r == false) {
            throw new RuntimeException();
        }

        isLegal(list);
        assertElementsNumber(list, 4);
        assertDesignatedSpotElement(list, 0, 2000);
        assertDesignatedSpotElement(list, 1, 200);
        assertDesignatedSpotElement(list, 2, 300);
        assertDesignatedSpotElement(list, 3, 1000);


        // [2000, 200, 300, 1000]
        list.add(200L);
        list.add(200L);
        // [2000, 200, 300, 1000, 200, 200]
        r = list.remove(200L);
        // [2000, 300, 1000, 200, 200]
        if (r == false) {
            throw new RuntimeException();
        }

        isLegal(list);
        assertElementsNumber(list, 5);
        assertDesignatedSpotElement(list, 0, 2000);
        assertDesignatedSpotElement(list, 1, 300);
        assertDesignatedSpotElement(list, 2, 1000);
        assertDesignatedSpotElement(list, 3, 200);
        assertDesignatedSpotElement(list, 4, 200);

       r = list.remove(5000L);
       if(r == false){
           throw new RuntimeException();
       }

    }
}
